package Leetcode.动态规划;

public class YangtzeBoatRental {

    // 计算从游艇出租站1到出租站n所需的最少租金
    public int minCost(int[][] costs, int n) {
        // dp[i][j] 表示从出租站i到出租站j所需的最少租金
        int[][] dp = new int[n][n];

        // 初始化dp数组
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j] = Integer.MAX_VALUE; // 初始化为最大值
            }
            dp[i][i] = 0; // 同一站点的租金为0
        }

        // 填充dp数组
        for (int len = 2; len <= n; len++) { // 遍历所有可能的区间长度
            for (int i = 0; i <= n - len; i++) { // 遍历所有可能的起点
                int j = i + len - 1; // 计算终点
                for (int k = i + 1; k <= j; k++) { // 遍历所有可能的中间点
                    if (dp[i][j] > dp[i][k - 1] + costs[i][k] + dp[k][j]) {
                        dp[i][j] = dp[i][k - 1] + costs[i][k] + dp[k][j]; // 更新最少租金
                    }
                }
            }
        }

        // 返回从出租站1到出租站n的最少租金
        return dp[0][n - 1];
    }

    // 递归函数计算从游艇出租站i到出租站j的最少租金
    public int minCost(int[][] costs, int i, int j) {
        // 如果i大于等于j，表示同一个站点或者不存在这样的路线，返回0
        if (i >= j) {
            return 0;
        }
        // 计算从i到j的最少租金
        int minCost = Integer.MAX_VALUE;
        for (int k = i + 1; k <= j; k++) {
            int cost = minCost(costs, i, k - 1) + costs[i][k] + minCost(costs, k, j);
            if (cost < minCost) {
                minCost = cost;
            }
        }
        return minCost;
    }

    public static void main(String[] args) {
        // 假设costs[i][j]表示从出租站i到出租站j的租金，其中1<=i<j<=n
        // 例如，costs[0][1]表示从出租站1到出租站2的租金
        int[][] costs = {
            {0, 5, 15, 20},
            {0, 0, 10, 10},
            {0, 0, 0, 10},
            {0, 0, 0, 0}
        };
        int n = 4; // 游艇出租站的数量

        YangtzeBoatRental rental = new YangtzeBoatRental();
        int minCost = rental.minCost(costs, n);
        System.out.println("从游艇出租站1到出租站n所需的最少租金为: " + minCost);

        minCost = rental.minCost(costs, 0, n - 1);
        System.out.println("从游艇出租站1到出租站n所需的最少租金为: " + minCost);
    }
}
